package org.zxp.algorithm.sort;

import org.zxp.algorithm.sort.utils.Tools;

/**
 * @program: effectiveJava
 * @description:一个无序数组查找第K大的元素
 * @author: X-Pacific zhang
 * @create: 2019-07-28 15:59
 **/
public class QuickSortKth {

    public static void main(String[] args){
        int[] sorts = {4,5,3,2,7,9,2,5};
        int result = QuickSortKth.quick_find(sorts, 0, sorts.length-1, 8);
        System.out.println(result);
    }

    public static int quick_find(int[] a, int p, int r,int k){
        int q = QuickSortKth.partition(a,p,r);//获取一个点并获取此点的下标
        if(k == q + 1){
            return a[q];
        }else if(k < q + 1){
            return quick_find(a,p,q-1,k);
        }else{
            return quick_find(a,q+1,r,k);
        }
    }

    public static int partition(int[] a, int p, int r) {
        int i = p, j = p;//i-1为已经排好的范围，j为遍历的游标
        int pivot = a[r];//以最末尾的点为分界点
        while (true) {//并将大于此点的数据移动到右边，小于此点的数据移动到左边
            if (j == r) {//当遍历的游标到了数组末尾则把i的位置与末尾元素互换，并返回下标作为q点下标
                int tmp = a[i];
                a[i] = a[r];
                a[r] = tmp;
                return i;
            }
            if (a[j] <= pivot) {//如果小于末尾值，则i，j交换
                int tmp = a[i];
                a[i++] = a[j];
                a[j] = tmp;
            }//移动下标
            j++;
        }
    }




}
